Griesmer Bound

In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of Linear code, linear Binary coding, binary Block code, codes of dimension ''k'' and minimum distance ''d''.
There is also a very similar version for non-binary codes.

Statement of the bound

For a binary linear code, the Griesmer bound is:

: $n\geqslant \sum_^ \left\lceil\frac\right\rceil.$

Proof

Let $N(k,d)$ denote the minimum length of a binary code of dimension ''k'' and distance ''d''. Let ''C'' be such a code. We want to show that

:$N(k,d)\geqslant \sum_^ \left\lceil\frac\right\rceil.$

Let ''G'' be a generator matrix of ''C''. We can always suppose that the first row of ''G'' is of the form ''r'' = (1, ..., 1, 0, ..., 0) with weight ''d''.
: $G= \begin 1 & \dots & 1 & 0 & \dots & 0 \\ \ast & \ast & \ast & & G' & \\ \end$

The matrix $G'$ generates a code $C'$, which is called the residual code of $C.$ $C'$ obviously has dimension $k'=k-1$ and length $n'=N(k,d)-d.$ $C'$ has a distance $d',$ but we don't know it. Let $u\in C'$ be such that $w(u)=d'$. There exists a vector $v\in \mathbb_2^d$ such that the concatenation $(v, u)\in C.$ Then $w(v)+w(u)=w(v, u)\geqslant d.$ On the other hand, also $(v, u)+r\in C,$ since $r\in C$ and $C$ is linear: $w((v, u)+r)\geqslant d.$ But

:$w((v, u)+r)=w(((1,\cdots,1)+v), u)=d-w(v)+w(u),$

so this becomes $d-w(v)+w(u)\geqslant d$. By summing this with $w(v)+w(u)\geqslant d,$ we obtain $d+2w(u)\geqslant 2d$. But $w(u)=d',$ so we get $2d'\geqslant d.$ As $d'$ is integral, we get $d'\geqslant \left\lceil \tfrac \right\rceil.$ This implies

:$n'\geqslant N\left (k-1,\left\lceil \tfrac \right\rceil \right ),$

so that

:$N(k,d)\geqslant d + N\left (k-1, \left\lceil \tfrac \right\rceil \right ).$

By induction over ''k'' we will eventually get

:$N(k,d)\geqslant \sum_^ \left\lceil\frac\right\rceil.$

Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity

:$\left\lceil\frac\right\rceil = \left\lceil\frac\right\rceil$

for any integer ''a'' and positive integer ''k''.

The bound for the general case

For a linear code over $\mathbb_q$, the Griesmer bound becomes:

: $n\geqslant \sum_^ \left\lceil\frac{q^i}\right\rceil.$

The proof is similar to the binary case and so it is omitted.

See also

*Singleton bound
*Hamming bound
*Gilbert-Varshamov bound
*Johnson bound
*Plotkin bound
* Elias Bassalygo bound

References

*J. H. Griesmer, "A bound for error-correcting codes," IBM Journal of Res. and Dev., vol. 4, no. 5, pp. 532-542, 1960.

Coding theory
Articles containing proofs